|
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.〔Harold W. Kuhn, "The Hungarian Method for the assignment problem", ''Naval Research Logistics Quarterly'', 2: 83–97, 1955. Kuhn's original publication.〕〔Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", ''Naval Research Logistics Quarterly'', 3: 253–258, 1956.〕 James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial.〔J. Munkres, "Algorithms for the Assignment and Transportation Problems", ''Journal of the Society for Industrial and Applied Mathematics'', 5(1):32–38, 1957 March.〕 Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was , however Edmonds and Karp, and independently Tomizawa noticed that it can be modified to achieve an running time. Ford and Fulkerson extended the method to general transportation problems. In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.〔http://www.lix.polytechnique.fr/~ollivier/JACOBI/jacobiEngl.htm〕 ==Simple explanation of the assignment problem== In this simple example there are three workers: Jim, Steve, and Alan. One of them has to clean the bathroom, another sweep the floors, and the third wash the windows, but they each demand different pay for the various tasks. The problem is to find the lowest-cost way to assign the jobs. The problem can be represented in a matrix of the costs of the workers doing the jobs. For example: The Hungarian method, when applied to the above table, would give the minimum cost: this is $6, achieved by having Jim clean the bathroom, Steve sweep the floors, and Alan wash the windows. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hungarian algorithm」の詳細全文を読む スポンサード リンク
|